package com.lql.seek;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * 斐波那契数列
 */
public class Fibonacci {
    public static void main(String[] args) {
        int[] ints = UnRecursionFibonacci(10);
        System.out.println(Arrays.toString(ints));
        System.out.println(recursionFibonacci(10, 1, 1));
        System.out.println(recursionFibonacciNo(10));
    }

    /**
     * 非递归的方式(数组)实现斐波那契数列
     *
     * @param maxsize 生成的斐波那契数列的长度
     * @return 返回生成的斐波那契数列
     */
    public static int[] UnRecursionFibonacci(int maxsize) {
        int[] fibonacci = new int[maxsize];
        fibonacci[0] = 1;
        fibonacci[1] = 1;
        for (int i = 2; i < maxsize; i++) {
            fibonacci[i] = fibonacci[i - 1] + fibonacci[i - 2];
        }
        return fibonacci;
    }

    /**
     * 递归的方式实现斐波那契数列，优化后的，防止栈溢出，尾递归
     *
     * @param fibonacci 生成的斐波那契数列的长度
     * @return 返回生成的斐波那契数列
     */
    public static int recursionFibonacci(int fibonacci, int i, int j) {
        if (fibonacci == 1 || fibonacci == 2) {
            return j;
        }
        return recursionFibonacci(fibonacci - 1, j, j + i);
    }

    /**
     * 递归的方式实现斐波那契数列，未优化，会发生栈溢出
     *
     * @param fibonacci 生成的斐波那契数列的长度
     * @return 返回生成的斐波那契数列
     */
    public static int recursionFibonacciNo(int fibonacci) {
        if (fibonacci == 1 || fibonacci == 2) {
            return 1;
        }
        return recursionFibonacciNo(fibonacci - 1) + recursionFibonacciNo(fibonacci - 2);
    }
}
